﻿#pragma once
#include "Index.h"

class ILargeNumbersSum
{
public:
	/**
	 * 大数加法
	 *
	 * 以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
	 * 数据范围：s.length, t.length≤100000，字符串仅由'0'~‘9’构成
	 * 要求：时间复杂度O(n)
	 */
	virtual std::string Sum(std::string a, std::string b) = 0;
};

/**
 * 大数问题
 */
class LargeNumbersSumSolution:public ILargeNumbersSum
{
public:
	//9ms 1996kB
	class LargeNumbersSum:public ILargeNumbersSum
	{
	public:	std::string Sum(std::string a, std::string b) override
	{
		if (a.empty() && b.empty())
			return "";

		int i1 = a.size() - 1;
		int i2 = b.size() - 1;
		std::stack<int> nums_stack;

		int carry = 0;
		while (i1 >= 0 || i2 >= 0 || carry > 0)
		{
			int sum = 0;
			if (i1 >= 0)
				sum += a[i1--] - '0';
			if (i2 >= 0)
				sum += b[i2--] - '0';
			sum += carry;

			nums_stack.push(sum % 10);
			carry = sum / 10;
		}

		std::string sum_str;
		while (!nums_stack.empty())
		{
			sum_str += static_cast<char>(nums_stack.top() + '0');
			nums_stack.pop();
		}
		return sum_str;
	}
	};
	//8ms 1452kB
	class LargeNumbersSumV2:public ILargeNumbersSum
	{
	public:	std::string Sum(std::string a, std::string b) override
	{
		//其中一个加数为空的情况
		if (a.empty()) return b;
		if (b.empty()) return a;

		const int alloc_size = std::max<>(a.size(), b.size());
		//最后和的结果
		std::string add_sum(alloc_size + 1, ' ');
		std::string::reverse_iterator rit_sum = add_sum.rbegin();
		//进位数
		int carry = 0;
		std::string::reverse_iterator rit_of_a = a.rbegin();
		std::string::reverse_iterator rit_of_b = b.rbegin();

		//逐位相加
		while (rit_of_a != a.rend() || rit_of_b != b.rend() || carry > 0)
		{
			int sum = 0;
			if (rit_of_a != a.rend())
			{
				sum += *rit_of_a - '0';
				++rit_of_a;
			}
			if (rit_of_b != b.rend())
			{
				sum += *rit_of_b - '0';
				++rit_of_b;
			}
			sum += carry;
			const auto sumed_char = static_cast<char>((sum % 10) + '0');
			*rit_sum++ = sumed_char;
			carry = sum / 10;
		}

		if (add_sum[0] == ' ')
			return add_sum.substr(1);
		else
			return add_sum;
	}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>

class LargeNumbersSumTest :public testing::Test
{
protected:
	void SetUp() override
	{
		Solutions = {
			new LargeNumbersSumSolution::LargeNumbersSum,
			new LargeNumbersSumSolution::LargeNumbersSumV2,
		};
	}
	void TearDown() override
	{
		STLUtil::ClearVector(Solutions);
	}
	std::vector<ILargeNumbersSum*> Solutions;
};

TEST_F(LargeNumbersSumTest, Sum)
{
	std::string a = "21324288893292";
	std::string b = "923128290481290239021902910";

	for (const auto solution : Solutions)
	{
		auto sum_result = solution->Sum(a, b);
		EXPECT_EQ(sum_result, "923128290481311563310796202");
	}

	a = "1";
	b = "99";
	for (const auto solution : Solutions)
	{
		auto sum_result = solution->Sum(a, b);
		EXPECT_EQ(sum_result, "100");
	}
}
#endif